package binary_search.leetcode_34_medium;

public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int firstPosition = findFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }
        int lastPosition = findLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }

    /**
     * 寻找结束位置
     * <p>
     * 当nums[mid] 严格大于target时， mid及其右边都肯定不存在 target， 所以 right = mid - 1
     * 当nums[mid] 等于target时， 此时mid可能就是开始位置或结束位置， 但是寻找的是结束位置，所以 left = mid
     *      当left = mid时，取中位数时，要向上取整， int mid = left + (right - left + 1) / 2;
     *      为什么这么做？
     *          当区间只剩下两个元素时：[0,1]。 设目标值target = 0
     *          计算mid = (0 + 1) / 2 = 0;
     *          对应的nums[0] = 0;  此时 left = mid 将会发生什么？
     *              left 仍然 等于0， right仍然 等于1， mid仍然等于0， nums[mid]仍然 等于0
     *              left 永远 小于right 造成死循环。
     *      所以，在选择中位数时，要向上取整，
     *          这样 mid = ( 0 + 1 + 1 ) / 2 = 1, nums[1] = 1;
     *          1 > target; right = mid - 1 , left == right 循环结束，此时区间之下1个元素，再循环外单独进行判断。
     *
     * 当nums[mid] 严格小于target时， mid及其左边都肯定不存在 target， 所以 left = mid + 1
     */
    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            //注意！！！！！！！
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                left = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 寻找开始位置
     * <p>
     * 当nums[mid] 严格大于target时， mid及其右边都肯定不存在 target， 所以 right = mid - 1
     * 当nums[mid] 等于target时， 此时mid可能就是开始位置或结束位置， 但是寻找的是开始位置，所以 right = mid
     * 当nums[mid] 严格小于target时， mid及其左边都肯定不存在 target， 所以 left = mid + 1
     */
    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        /*
            此时需要额外的判断nums[left] 是否等于 target
                如果 等于target，则left就是target的开始位置
                否则，说明数组中不存在target，返回-1
         */
        return nums[left] == target ? left : -1;
    }

}
